package chapter03;

import java.util.ArrayList;
import java.util.List;

public class Generate118 {
    /**
     * .  第一层
     * . .  第二层
     * . . .  第三层
     * . . . .  第四层
     * 观察发现每一层最外围的数字都是1，其余是上层值加左上角值之和
     * 用数组pre记录上层值 每次循环一层修改pre 为了方便计算，下标从1开始
     * 假设当前层为row col->[1,row] 当前记录层为cur
     * 1).col==1||col==row
     *      cur[col]=1
     * 2).其他情况
     *      cur[col]=pre[col]+pre[col-1]
     * 循环结束后 cur赋值给pre
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res=new ArrayList<>();
        int[] pre=null;
        for(int row=1;row<=numRows;row++){
            List<Integer> path=new ArrayList<>();
            int[] cur=new int[row+1];
            for(int col=1;col<=row;col++){
                if(col==1||col==row){
                    cur[col]=1;
                }else{
                    cur[col]=pre[col]+pre[col-1];
                }
                path.add(cur[col]);
            }
            pre=cur;
            res.add(path);
        }
        return res;
    }
}
